Rochambeau Judge Identification

There are N children playing the Rochambeau (scissors‐rock‐cloth) game with you. One child is acting as the judge, while the remaining N-1 children are partitioned into three groups. In every round, two children are chosen arbitrarily to play a single turn; you are given only the result (win/lose/draw) but not the gestures they presented. It is known that:

• If two children belong to the same group, they always show the same gesture and the game ends in a draw.
• If two children (who are not the judge) belong to different groups, then their gestures are distinct. Moreover, the outcome is determined by the standard rock‐paper‐scissors rules. Here we adopt the following convention: assign each gesture an integer in \(\{0,1,2\}\) where the rule is that for a match (a, b) with outcome A (i.e. the first child wins), the condition is \[ group(b) \equiv group(a)+1 \; (\mathrm{mod}\;3), \] and for outcome B (the second child wins) the relation is \[ group(a) \equiv group(b)+1 \; (\mathrm{mod}\;3). \]
• The judge picks his/her gesture uniformly at random in each round (so his/her play does not follow any group rule).

You do not know who the judge is nor how the remaining children are grouped. After M rounds the game ends. Based solely on the outcomes (with no knowledge of the actual gestures), determine whether you can uniquely identify the judge. If yes, output the earliest round number (1-indexed) after which the judge can be uniquely determined; otherwise output -1.

Note: When evaluating a candidate as the judge, ignore any round in which this candidate participates. For the remaining rounds, treat the outcome as a constraint on the group assignments among the other children. In particular:

• If the outcome is draw (denoted by D), then the two children must have the same group (i.e. their group difference is 0 modulo 3).
• If the outcome is A, then the constraint is \(group(b) \equiv group(a)+1 \; (\mathrm{mod}\;3)\).
• If the outcome is B, then the constraint is \(group(a) \equiv group(b)+1 \; (\mathrm{mod}\;3)\).

Your task is to simulate the rounds (in the given order) and for each round check, for every candidate, whether there is a valid assignment of groups (values in \(\{0,1,2\}\)) for all children other than that candidate that satisfies all constraints induced by rounds in which the candidate did not play. Output the earliest round where exactly one candidate is possible as the judge.

inputFormat

The first line contains two integers N and M (number of children and number of rounds).

Each of the following M lines contains a description of a round in the format:

a b r

where a and b (1-indexed) are the two children chosen for that round and r is a character that can be:

• D: indicating a draw
• A: indicating that the first child won (so the constraint is \(group(b) \equiv group(a)+1\) mod 3)
• B: indicating that the second child won (so the constraint is \(group(a) \equiv group(b)+1\) mod 3)

outputFormat

Output a single integer: the earliest round after which the judge can be uniquely identified, or -1 if it is impossible to do so by the end of M rounds.

sample

4 8
2 3 A
3 4 A
4 2 A
1 3 A
1 4 A
1 3 B
1 2 B
1 2 A

8