After an adventure, Farnsworth has decided to mass-manufacture and market his mind/body-switching device. Given any pairing of bodies, the device can switch the minds inhabiting them once -- the device will not operate on the same pairing of bodies a second time.
In light of this design flaw, Tate and Dixon (two Globetrotters) sense a very lucrative consulting opportunity. Once a group of users can no longer stand the confusion and wish for their proper mind/body relationships to be restored, Tate and Dixon offer their services (at a very competitive and not at all exploitative market rate, mind you) by using their own bodies to help, Tate and Dixon then switch everybody's mind back into their proper body (Note that each group of customers uses a different copy of the mind-switching device, so that Tate and Dixon's bodies can switch minds once per group of customers).
After a few months, Tate and Dixon hire you to help with the sorting problems---it's hard for them to keep their own minds on it nowadays. Your task is as follows: given a sequence of mind/body swaps, provide another subsequent sequence of swaps such that all swaps (new and old, combined) are distinct and each body ends up with its rightful mind.
Warn: 本題有 specialjudge
Each input case begins with two space-separated numbers N and M on a single line, where 1<= N,M<= 100000.
The number N denotes the number of customers, labelled 0,1,...,N-1;
Tate and Dixon are numbered N and N+1, respectively.
Also, M denotes the number of swaps already performed by the device.
The next line consists of 2M space-separated numbers:
Input is followed by a single line with N=0, which should not be processed.
For each test case, output on a single line any sequence of space-separated numbers
4 3 0 1 2 3 0 2 4 6 0 1 2 3 0 2 1 3 0 3 1 2 100000 0 100000 1 0 1 100000 1 0 1 0
1 3 0 3 1 2 0 1 2 3 0 2 1 3 0 3 1 2 2 3 0 2 1 3 0 3 1 2 100001 3 0 100001 1 3 0 3 1 100001
Migrated from old NTUJ.
2010 Stanford Local Round 2
| No. | Testdata Range | Score |
|---|