5 8
2 4 1
2 3 3
2 5 6
1 5 3
1 4 3
2 6 4
2 2 3
2 6 3
ans:4

5 8
1 1 1
1 2 2
1 4 6
2 4 6
1 5 3
1 3 1
2 2 3
1 2 3
ans:3

5 8
1 6 3
2 2 6
1 4 3
1 1 2
2 2 3
2 6 3
1 2 3
2 1 6
ans:5

5 8
1 4 5
2 6 1
1 3 6
2 6 5
1 1 2
2 5 2
1 1 4
1 1 1
ans:4

5 8
2 1 4
2 4 4
2 1 6
1 4 5
2 1 5
2 6 3
1 1 6
2 5 1
ans:5

5 8
1 4 5
2 4 3
2 1 3
1 2 3
2 4 1
2 4 1
1 1 4
2 1 3
ans:2

5 8
1 3 1
2 5 5
1 4 4
2 2 5
2 1 6
1 2 6
2 2 5
2 4 5
ans:3

5 8
1 5 3
2 5 3
1 4 5
1 5 6
1 1 1
1 2 6
1 2 6
1 6 2
ans:5

5 8
1 4 4
2 6 6
1 2 3
2 1 4
1 3 2
2 1 1
2 1 6
2 3 1
ans:3

5 8
1 5 6
1 6 6
1 6 6
1 1 6
1 6 4
1 6 1
2 3 6
1 5 5
ans:7

5 8
1 3 5
2 6 3
2 6 6
1 6 1
2 3 3
2 1 4
2 2 4
2 2 1
ans:5

5 8
1 3 2
2 4 5
1 4 2
1 2 3
1 2 2
1 1 1
2 2 2
1 6 4
ans:2

5 8
1 5 5
1 2 5
1 6 3
2 3 1
2 2 4
1 3 3
1 3 2
2 6 6
ans:2

5 8
1 4 6
1 3 1
1 6 2
1 1 5
1 1 5
1 6 1
1 3 6
2 2 4
ans:4

5 8
1 4 3
1 4 4
1 2 4
1 1 4
2 5 1
2 2 5
2 6 2
1 5 5
ans:2

5 8
2 4 6
1 4 3
2 6 6
1 5 5
1 5 5
1 4 5
1 4 1
2 3 5
ans:3

5 8
2 4 1
2 1 6
2 2 4
2 2 3
1 2 3
1 4 3
1 3 3
2 3 5
ans:2

5 8
2 5 1
1 2 2
1 3 5
1 3 1
2 2 4
2 2 3
1 5 6
2 2 4
ans:2

5 8
1 2 4
1 4 3
2 2 4
2 2 2
2 4 5
1 1 5
2 5 6
1 6 3
ans:4

5 8
2 6 1
2 3 3
1 1 6
1 1 3
1 5 2
2 1 2
2 3 5
2 3 4
ans:3

5 8
2 1 3
2 3 5
1 1 1
2 4 1
2 3 2
1 4 1
2 6 2
1 6 1
ans:3

5 8
1 2 4
1 1 3
1 6 5
1 6 3
1 4 1
1 3 3
1 2 4
1 3 4
ans:2

5 8
2 1 3
2 1 4
1 3 4
1 4 4
1 2 3
1 6 4
2 2 3
1 5 6
ans:3

5 8
2 2 1
2 1 1
2 4 4
2 5 2
1 1 1
1 5 2
1 5 3
1 5 3
ans:3

5 8
1 2 4
2 6 4
2 6 5
1 1 5
1 6 1
1 5 2
1 6 5
1 3 1
ans:4

5 8
2 2 4
2 5 3
1 6 2
1 2 2
1 6 4
2 2 1
1 3 6
1 4 5
ans:3

5 8
1 2 4
1 5 3
2 5 3
2 1 1
2 4 1
1 4 6
1 2 2
1 3 2
ans:3

5 8
2 2 2
2 3 1
1 1 6
2 5 5
1 4 4
1 5 5
1 6 6
1 1 3
ans:5

5 8
2 6 4
2 5 3
2 6 5
1 4 6
1 3 4
1 1 3
2 5 5
1 1 3
ans:4

5 8
2 1 3
1 6 2
1 4 6
1 5 5
2 3 2
2 1 3
1 1 6
2 6 1
ans:4

5 8
2 5 3
1 6 2
2 5 2
1 1 4
2 2 5
1 2 3
1 6 1
2 4 6
ans:4

5 8
1 3 3
1 6 5
2 6 3
1 3 2
1 6 6
1 2 2
2 5 6
2 4 4
ans:5

5 8
2 3 1
1 5 4
2 6 3
2 3 3
1 4 3
2 4 2
1 6 3
2 2 5
ans:4

5 8
1 1 1
1 5 5
1 5 3
1 5 5
2 1 6
1 4 2
1 1 6
2 1 2
ans:2

5 8
2 1 2
2 5 5
2 2 5
2 2 4
1 6 5
2 5 4
2 4 6
2 6 1
ans:5

5 8
2 6 1
1 4 4
2 3 4
1 2 6
1 2 2
2 4 1
1 2 6
2 2 3
ans:3

5 8
2 1 6
2 5 1
1 4 1
2 2 1
2 5 3
1 2 6
1 4 1
2 6 4
ans:3

5 8
2 2 3
1 1 5
2 2 3
1 6 1
2 3 3
2 4 6
1 5 5
2 1 1
ans:4

5 8
2 3 5
2 3 2
2 3 1
1 5 1
1 6 6
2 3 5
1 1 3
1 2 6
ans:3

5 8
1 5 2
1 6 2
1 1 4
2 6 6
1 2 6
2 5 3
2 2 3
1 1 5
ans:3

5 8
2 6 1
2 2 2
1 5 2
2 4 5
2 4 1
2 1 5
2 6 4
1 2 2
ans:4

5 8
2 2 1
2 6 2
1 6 4
1 3 6
2 5 6
2 1 6
2 6 2
2 5 4
ans:6

5 8
2 5 4
2 5 1
2 1 4
1 2 2
1 2 1
2 6 3
1 1 4
1 4 6
ans:3

5 8
1 6 2
1 5 1
1 1 5
1 1 5
1 3 6
2 5 3
1 4 5
2 2 1
ans:2

5 8
2 2 2
2 6 1
2 1 5
2 2 2
1 5 5
1 4 3
2 5 2
1 3 4
ans:3

5 8
1 3 3
1 1 3
2 5 2
1 3 3
2 5 4
2 5 4
1 2 6
1 3 4
ans:1

5 8
1 5 1
2 6 5
2 3 3
2 3 6
2 2 6
2 6 5
1 4 5
2 5 5
ans:6

5 8
1 4 4
1 5 5
1 4 5
2 5 4
2 3 6
2 6 3
1 5 2
1 5 6
ans:4

5 8
1 5 2
1 5 6
2 6 4
1 2 5
2 5 1
1 2 4
2 3 1
2 5 1
ans:2

5 8
2 3 6
2 3 5
1 6 4
2 2 4
2 5 6
1 4 5
2 4 5
1 5 2
ans:5

5 8
2 4 1
1 6 4
1 4 1
2 3 1
1 5 1
2 3 1
2 1 4
2 3 4
ans:4

5 8
1 2 4
2 5 2
2 1 2
2 5 2
1 1 1
1 4 1
2 2 5
2 5 4
ans:2

5 8
2 5 3
2 4 4
1 5 6
2 6 4
2 4 1
2 2 6
2 2 4
1 6 1
ans:5

5 8
1 4 4
2 4 1
2 2 1
2 2 2
1 5 3
2 1 4
1 2 2
1 1 3
ans:2

5 8
1 5 5
2 5 5
1 6 4
2 3 5
2 1 3
2 1 1
1 5 3
1 6 2
ans:5

5 8
2 2 4
1 2 2
2 2 2
2 4 6
2 2 2
1 3 5
2 2 1
1 4 2
ans:4

5 8
2 1 5
2 6 5
1 3 2
1 1 2
1 3 6
1 6 5
2 1 5
1 3 4
ans:3

5 8
1 3 4
1 5 4
2 4 6
1 1 5
2 3 6
2 4 3
1 5 5
1 4 4
ans:3

5 8
1 4 4
2 4 5
2 2 5
2 3 5
2 1 2
2 6 4
1 1 4
2 5 6
ans:3

5 8
1 3 3
2 6 5
1 5 5
2 4 3
2 4 2
1 5 5
2 2 3
2 2 2
ans:3

5 8
1 1 5
1 3 1
2 1 5
2 5 3
2 3 6
2 2 5
1 2 2
2 4 5
ans:3

5 8
1 4 6
1 5 6
2 1 5
1 2 5
1 1 3
1 2 5
2 6 3
1 5 2
ans:3

5 8
1 2 2
2 6 6
1 5 3
1 5 2
2 6 4
1 2 1
1 2 2
1 6 1
ans:3

5 8
2 3 1
2 4 2
2 3 5
2 1 6
2 2 4
2 4 6
1 2 2
1 2 3
ans:3

5 8
1 4 6
2 4 2
2 4 5
1 6 4
2 6 3
1 3 2
1 4 3
1 3 6
ans:5

5 8
2 6 4
1 2 2
2 2 2
2 4 1
2 5 4
2 2 4
2 4 3
2 2 2
ans:3

5 8
1 5 2
1 3 6
2 6 5
2 3 4
2 4 2
1 3 2
2 2 2
2 5 6
ans:5

5 8
1 2 2
1 3 5
1 6 4
1 1 3
2 4 1
2 3 5
2 1 4
2 4 1
ans:3

5 8
2 3 1
1 2 6
1 4 2
2 6 5
1 6 4
1 6 5
1 4 5
2 2 4
ans:5

5 8
2 4 3
2 5 6
2 4 2
2 1 2
1 2 3
2 1 6
2 2 5
2 3 3
ans:3

5 8
1 3 2
2 4 1
2 2 5
1 5 5
1 5 3
1 2 6
2 3 1
1 5 2
ans:3

5 8
1 4 5
2 1 4
2 5 6
2 5 3
1 2 2
2 5 4
1 6 3
2 6 1
ans:4

5 8
2 4 4
2 3 4
2 2 1
1 4 5
2 3 2
1 1 2
1 3 3
1 4 2
ans:2

5 8
1 4 1
2 3 6
2 4 6
1 5 6
1 4 3
2 1 4
2 2 4
2 2 5
ans:4

5 8
2 2 4
1 2 1
2 2 3
1 5 4
1 3 3
1 2 3
1 5 3
2 2 6
ans:2

5 8
1 5 5
1 2 1
1 5 3
1 2 3
1 1 4
2 3 4
2 6 6
1 2 6
ans:3

5 8
1 3 1
2 2 1
2 5 3
2 5 5
2 1 3
1 3 6
1 4 4
2 1 1
ans:4

5 8
2 6 1
1 4 6
1 3 3
2 2 1
2 2 1
1 2 2
2 3 4
1 4 3
ans:3