The Warring States Period (473-22l BC) refers to the centuries of turmoil following the Spring and Autumn Period. China was divided into many little kingdoms that were constantly fighting with each other. Unlike in previous ages, when chivalry played an important role in battles and the states fought mostly for balance of power or to resolve disputes, in this period the aim of battle was to conquer and completely annihilate the other states. Eventually seven states, known as the “Seven Great Powers” rose to prominence: Qi, Chu, Yan, Han, Zhao, Wei, and Qin. After numerous alliances and counter- alliances, Qin defeated all the other states one by one, putting an end to the Warring States Period. You are given a map that shows the position of the capital for each state, and the borders between the states as a series of line segments. Your job is to determine which states were fighting with each other. This is pretty easy to determine — if two states had a common border, then they were fighting. Input The input contains several bloks of test cases. Each case begins with a line containing two integers: the number l ≤ n ≤ 600 of states, and the number l ≤ m ≤ 4000 of border segments. The next n lines describe the coordinates of capitals, there are two integers in each line. The next m, lines after that describe the m, border segments. Each line contains four integers. x1, y1, x2 and y2, meaning that there is a border segment from (x1,y1) to (x2,y2). (It is not given in the input what the two states on the two sides of the border are, but it can be deduced from the way the borders go.) Each state is enclosed by a continuous borderline. The states are surrounded by an infinite waste- land, thus a border segment either separates two states, or a state from the wasteland. It is not possible that the same state is on both sides of a border segment, or the wasteland is on both sides of a border segment. There is exactly one capital in each state, and there is no capital in the wasteland. The border segments do not cross each other, they can meet only at the end points. The input is terminated by a block with n = m = 0. Output For each test case, you have to output n lines that describe the enemies of the n states (recall that if two states share a border, then they are enemies). Each line begins with an integer, the number x of enemies the given state has. This number is followed by x numbers identifying the enemies of the state. These numbers are between 1 and n and number 1 refers to the first capital appearing in the input, number n refers to the last. Sample Input 4 12 32 11 8 12 17 1 19 0 0 10 0 10 0 20 0 20 0 20 10 20 10 20 20 20 20 10 20
2/2 10 20 0 20 0 20 0 10 0 10 0 0 10 0 10 10 0 10 10 10 20 10 10 10 10 20 10 10 4 19 10 190 30 170 50 150 100 70 140 0 140 140 140 140 60 140 60 140 60 0 200 0 200 200 200 200 0 200 0 200 0 0 160 0 160 160 160 160 40 160 40 160 40 0 180 0 180 180 180 180 20 180 20 180 20 0 0 0 20 0 20 0 40 0 40 0 60 0 60 0 140 0 140 0 160 0 160 0 180 0 180 0 200 0 00 Sample Output 224 213 224 213 12 213 224 13