In each cell of a 100 x 100 table, one of the integers 1,2,...,5000 is written. Moreover, each integer appears in the table exactly twice. Prove that one can choose 100 cells in the satisfying three conditions below.
(1) Exactly one cell is chosen in each row.
(2) Exactly one cell is chosen in each column.
(3) The numbers in the cells chosen are pairwise distinct
