You have recently been ap- pointed as the administrator for a wired network of de- vices. Unfortunately, your predecessor used very poor quality lines to connect the devices. The board of exec- utives is currently deciding if they want to fund an upgrade to a wireless network, or sim- ply replace the existing wires with ones of better quality. As expected, this decision is being weighed down with bu- reaucratic nonsense; it looks like it will take some time be- fore anything is approved. Meanwhile, you still have to deal with the problem at hand. You have access to an antiquated version of Newton Network Monitor which is a software package that, once installed on a machine, will monitor all lines connected to that machine and immediately alert the user when a line has failed. This should help reduce your response time to any failures. Your task is to install the software on some machines so each line is being monitored by at least one of its endpoint devices. For various technical reasons, the time it takes to install the software varies from device to device so you want to minimize the total amount of time spent installing the software. You cannot install on more than one machine at a time (since you only have one copy of the software) meaning the total time spent installing the software is exactly the sum of the installation times on each machine. Input Each input case begins with two numbers n, m with 1 ≤ n ≤ 1, 000 and 0 ≤ m ≤ 25, 000. Following this are m pairs of distinct integers between 0 and n − 1 which describe a wire connecting the two devices. The time spent installing the software on machine numbered i is 2i. The input is terminated with n = m = 0; this should not be processed. Output For each input case, there is to be one line of output containing a sequence of n bits with no spaces. The i-th bit is 1 if the software is installed on machine i, and 0 if not. Sample Input 32
2/2 02 12 31 12 00 Sample Output 110 010