5 12
1 2 a
3 2 c
1 4 c
4 3 c
3 1 c
4 1 a
3 4 a
5 4 c
3 5 a
2 3 a
2 1 c
5 3 a
4
5 2 3 1