1 人解决，4 人已尝试。
1 份提交通过，共有 7 份提交。
9.9 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
For several years now, the Nordic Conference on Partitions and Combinatorics, NCPC, has had a growing number of participants. This year the organizing team is expecting an all time high record in the hundreds. Due to the politics of arranging this prestigious event, the conference site was decided a long time ago to be the Grand Hotel in Stockholm. The hotel has two large dining halls, but unfortunately, each of these halls alone can only fi t up to two thirds of the NCPC participants, so the participants are going to have to be divided in two groups.
This constraint calls for some thinking on behalf of the organizing team for the conference dinner: could they come up with some division of the participants in two parts, none of which is larger than 2/3 of the entire group, meeting some witty division rule suitable for the occasion, which they could tell the participants for their amusement? After all, as long as there is some grand logic rule to which of the two dining halls you are being seated in, you (as a mathematician) would be happy! They thought for a while and came up with the following idea for the division: Is there a year Y and a division of the participants in two parts such that every pair in the first part met for the rst time some time before year Y , and every pair in the second part met for the fi rst time some time in or after year Y ? Now this clearly quali ed as an appropriate rule to all of them, but the question was whether it would be possible?
The fi rst line of input contains an integer 4 ≤n ≤400, the number of participants, and c, the number of known fi rst encounters. The next c lines are each in the format a b y, meaning participant a and b (1 ≤a < b ≤n) met for the fi rst time in year y (1948 ≤y < 2008). No pair of participants will appear more than once on the list, and every pair of participants not in the list is assumed to have meet only now (in the year 2008).
For each test case, either the smallest year Y such that it is possible to divide the participants in two parts, neither of which contains more than 2n/3 people, such that all people in the first part rst met before year Y , and all people in the second part first met in or after year Y . If there is no such year, output the string ‘Impossible’.
4 6 1 2 1987 2 3 1987 1 3 1987 2 4 1987 1 4 1987 3 4 1987 /* 6 3 1 2 1970 3 4 1980 5 6 1990 */
Impossible /* 1971 */
1 人解决，4 人已尝试。
1 份提交通过，共有 7 份提交。
9.9 EMB 奖励。