32509번 - 세 트리 스페셜 저지

문제

$N$ 개의 정점과 $M$ 개의 양방향 간선을 가진 그래프가 주어진다. 그래프의 정점은 1,ドル 2, \ldots, N$ 의 번호가 붙어 있다. 그래프에는 중복 간선과 루프가 존재할 수 있다.

주어진 그래프에서 3ドル$ 개의 스패닝 트리를 찾아라. 이 때, 모든 간선은 최대 한 개의 스패닝 트리에 속해야 한다.

입력

첫 번째 줄에 두 정수 $N, M$ 이 주어진다. (2ドル \le N \le 500, 1 \le M \le 1,500円$)

이후 $M$ 개의 줄에 각 간선이 잇는 두 정점의 번호 $x, y$ 가 주어진다. (1ドル \le x, y \le N$)

출력

조건을 만족하는 3ドル$ 개의 스패닝 트리를 찾을 수 있다면, 길이 $M$ 의 문자열을 출력하라. 문자열의 각 문자는 0, 1, 2, 3으로 이루어져 있어야 한다. $i$ 번 문자가 0이면, 입력에서 $i$ 번째로 주어진 간선은 어떠한 스패닝 트리에도 속하지 않음을 의미한다. $i$ 번 문자가 1, 2, 3이면, 입력에서 $i$ 번재로 주어진 간선은 해당 번호의 스패닝 트리에 속함을 의미한다.

만약에 조건을 만족하는 3ドル$ 개의 스패닝 트리를 찾을 수 없다면 -1을 출력하라.

제한

힌트