题目链接:http://poj.org/problem?id=2912
Time Limit: 5000MS Memory Limit: 65536K

Description

N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for Mrounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

Input

Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 2,000) in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

Output

There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

Sample Input

3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0

Sample Output

Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

Problem solving report:

Description:有n个人玩剪刀石头布，编号为0~n-1,其中有且仅有一个人作为裁判，而其余人分成3组(组可以为空),这三个组分别只能出剪刀，石头和布，而裁判可以任意出,给出m次编号为a和编号为b的猜拳结果为c，要求输出最早在知道第几次猜拳结果后可以知道裁判是哪个人。
Problem solving:和食物链那道题差不多，使用并查集来维护。
由于裁判可以任意出，所以包含裁判的边都是不可靠的，所以不能在建立关系时不能纳入裁判。
枚举假设裁判为第i个人，每次假设都进行一次并查集操作;
假设当前裁判编号为i，那么枚举m次猜拳结果时，对有他参与的直接跳过;
那么，会出两种情况:出现矛盾，那么这个人不是裁判;没出现矛盾，这个人是裁判(当然这是建立在有且仅有一个裁判的基础上)。
如果出现枚举n个人假设作为裁判，发现全部都有矛盾呢，显然这代表裁判不存在了，根据题意是要输出“Impossible”;
如果出现两个及以上的人假设作为裁判，发现都没有矛盾，那么就不能判断谁是裁判了，输出“Can not determine”;

剩下的问题是，怎么知道是在知晓第几次猜拳结果后能断定谁是裁判了呢？

由于此时，枚举过程中，除去一个人(裁判)不会产生矛盾，剩下的n-1个人都会产生矛盾;
那么对于假设第i个人是裁判(但其实他并不是裁判)，那么我们记录下:枚举m次猜拳结果，第一个矛盾产生的位置，记录为pre[i](也就是说在pre[i]这次之后，就知道i不是裁判了);
显然，我们至少需要知晓max(pre[i])次猜拳结果之后，才能正确判断。

Accepted Code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int MAXN = 505;
using namespace std;
int f[MAXN * 3], pre[MAXN];
struct edge {
    char sym;
    int nua, nub;
}p[MAXN << 2];
int getf(int v) {
    if (f[v] != v)
        return f[v] = getf(f[v]);
    return v;
}
bool merge(int u, int v) {
    return !(getf(u) != getf(v));
}
void Union(int u, int v) {
    int t1 = getf(u);
    int t2 = getf(v);
    if (t1 != t2)
        f[t2] = t1;
}
int main() {
    int n, m, ans, cnt, line;
    while (~scanf("%d%d", &n, &m)) {
        memset(pre, -1, sizeof(pre));
        for (int i = 0; i < m; i++) {
            scanf("%d%c%d", &p[i].nua, &p[i].sym, &p[i].nub);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3 * n; j++)
                f[j] = j;
            for (int j = 0; j < m; j++) {
                if (p[j].nua != i && p[j].nub != i) {
                    int x = p[j].nua, y = p[j].nub;
                    if (p[j].sym == '>') {
                        if (merge(x, y) || merge(x, y + (n << 1))) {
                            pre[i] = j;
                            break;
                        }
                        Union(x, y + n);
                        Union(x + n, y + (n << 1));
                        Union(x + (n << 1), y);
                    }
                    else if (p[j].sym == '=') {
                        if (merge(x, y + n) || merge(x, y +(n << 1))) {
                            pre[i] = j;
                            break;
                        }
                        Union(x, y);
                        Union(x + n, y + n);
                        Union(x + (n << 1), y + (n << 1));
                    }
                    else {
                        if (merge(x, y) || merge(x, y + n)) {
                            pre[i] = j;
                            break;
                        }
                        Union(x, y + (n << 1));
                        Union(x + n, y);
                        Union(x + (n << 1), y + n);
                    }
                }
            }
        }
        ans = line = 0;
        for (int i = 0; i < n; i++) {
            if (!~pre[i]) {
                ans++;
                cnt = i;
            }
            else line = max(line, pre[i] + 1);
        }
        if (!ans)
            printf("Impossible\n");
        else if (ans > 1)
            printf("Can not determine\n");
        else printf("Player %d can be determined to be the judge after %d lines\n", cnt, line);
    }
    return 0;
}