#P2842. 魔法手镯
魔法手镯
题目描述
用 种颜色的珠子串成一个长度为 的环,每种颜色可以重复使用。给定 对不能相邻的颜色。相邻限制是双向的,可以禁止同种颜色相邻。最后一颗和第一颗也相邻。特别地,当 时,唯一的珠子和自身相邻。
只要两个环能通过旋转重合,就视为同一个方案。翻转后的方案只有在它也能通过旋转重合时才视为相同。求合法方案数对 取模后的值。
输入格式
第一行一个正整数 ,表示测试数据组数。每组数据的第一行给出三个整数 ,接下来 行各给出一对不能相邻的颜色编号 ()。
输出格式
对每组数据输出一行一个整数,表示合法方案数模 的值。
数据范围
,,,,且 。
样例
4
3 2 0
3 2 1
1 2
3 2 2
1 1
1 2
3 2 3
1 1
1 2
2 2
4
2
1
0