도로 우회

Nlogônia의 한 대도시 시청이 도로 포장 복구 사업을 시작했다. Nlogônia에서 모든 도로는 교차로 두 개를 직접 잇고, 일방통행이거나 양방향 통행이다. 오래된 왕실 칙령에 따라 이 도시에서는 어느 교차로에서 다른 어느 교차로로든 항상 갈 수 있는 경로가 하나 이상 있다.

복구 사업에서는 한 번에 도로 하나만 복구하며, 복구하는 동안 그 도로는 통행이 막힌다. 도로가 막히면 칙령을 어기게 되어 퇴근길이나 출근길이 끊기는 시민이 생길 수 있다. 시청은 일방통행 도로 일부를 양방향 도로로 바꿀 수 있지만, 양방향 도로에서 더 큰 사고가 나는 경향이 있어서 되도록 피하려 한다. 시청은 기존 일방통행 도로의 방향을 뒤집는 것만으로 우회로를 만드는 쪽을 선호한다.

국왕은 당신에게 프로그램 작성을 부탁했다. 도시의 도로 정보가 주어질 때, 주어진 도로 하나를 복구하려고 막은 뒤에도 다른 도로의 통행 방향을 바꿔서라도 모든 두 지점 사이에 경로가 계속 존재하도록 할 수 있는지 판단해야 한다.

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 파일 끝(EOF)까지 이어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($1 \le N \le 10^3$)과 $M$ ($1 \le M \le 10^5$)이 주어진다. 각각 교차로의 수와 도로의 수이다. 교차로는 $1$부터 $N$까지, 도로는 $1$부터 $M$까지의 정수로 번호가 매겨져 있다.

다음 $M$개의 줄에는 도로가 하나씩 주어진다. 각 줄은 세 정수 $A$, $B$ ($1 \le A, B \le N$), $T$ ($1 \le T \le 2$)로 이루어져 있다. $A$와 $B$는 도로가 직접 잇는 두 교차로이고, $T$는 통행 방향이다. $T = 1$이면 $A$에서 $B$로 가는 일방통행이고, $T = 2$이면 양방향 통행이다.

처음 주어지는 도로망은 칙령을 만족한다. 즉 어느 교차로에서 다른 어느 교차로로든 갈 수 있다. 가장 먼저 주어진 도로(1번 도로)가 복구를 위해 막히는 도로이다.

각 테스트 케이스마다 도로를 막은 뒤 칙령을 지키려면 시청이 무엇을 해야 하는지를 나타내는 문자 하나를 한 줄에 출력한다.

• -: 다른 도로를 전혀 바꿀 필요가 없다.
• *: 다른 도로를 어떻게 바꾸더라도 칙령을 지킬 수 없다.
• 1: 일방통행 도로 일부의 방향을 뒤집는 것만으로 칙령을 지킬 수 있다.
• 2: 칙령을 지킬 수 있지만, 일방통행 도로 일부를 양방향 도로로 바꿔야 한다.

네 경우는 이 순서대로 우선한다. 즉 위에서부터 처음으로 들어맞는 경우의 문자를 출력한다.