mit-indiv09-routing
All 100 residents (numbered 1, . . . , 100) of a far-away town write old-fashioned letters to each other. They don’t like email and they don’t have any regular mail service, so they deliver their own letters.
After a big storm blows through, they’re written a lot of letters that need delivering. Each person still has all of the letters that they’ve written (each peson wrote at most 100 letters), and each letter is addressed to someone (some people in town are eccentric and might have written letters to themselves, but no one has more than 100 letters addressed to him or her).
They want to deliver all the letters, but they don’t think it’s any fun if anyone gives anyone else a big stack of letters. So they decide that each person may hand each other person no more than 10 letters. Of course, this might be impossible if everyone were to hand all of the letters they wrote directly to the letters’ addressees, but letters can be handed off as many times as needed on their way to their addressees.
Find a way for each of the letters to reach its addressee.
Each subsequent line describes one letter; the first number on that line is the number of the person who wrote that letter and the second number is the number of the person to whom the letter is addressed.
If you like, you may allow any given person to handle a letter more than once, but this seems silly, and if anyone hands a letter to him or herself, that counts as one of the ten times that that person may hand him or herself a letter.
Input:
11
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2Output:
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 3 2Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.