小O和小I一直喜欢打 UOJ 的比赛,然而等了半个丁酉年却也没能等到下一次比赛。眼看着 NOI 即将到来,他们决定一探究竟,找出 UOJ 沉寂的真正原因!
终于有一天,他们得知 UOJ 的管理层全都被两个一心想摧毁 OI 界的大魔王——滴滴诶柳和不响公座给封印起来。
这两个大魔王向来战略上联手对敌,战术上分工合作。每次滴滴诶柳首先给 oier 带来一堆麻烦;接着不响公座用超声波对 oier 进行催眠,降低 oier 们的反抗效率;关键时候滴滴诶柳又进行反向催眠,让 oier 拼命反击筋疲力尽。两个魔王轮流值班,有着充足的休息时间,而他们的对手却受到无间断攻击。最后随着时间的推移,oier 们的体力到了最低点时,不响公座放出大招,将 oier 封印起来。
要想拯救 UOJ,必须打败这两个魔王。小O和小I查阅资料,终于找到了获胜的方法——OI 阵。
首先,他们需要召集
同时他们意识到,当一个 oier 身边有同校的 oier 时,不响公座攻击的时候他们会聊起天来从而阵法被破;而反之,如果身边的人都不熟悉,则会产生表现欲,有效抗住不响公座的超声波攻击。因此他们要求,图中任意两个相邻的 oier 来自不同的学校。
现在已知这张图的构成。该图具有
小O想要知道有多少种布阵方式,但是鉴于小I最多只能数到
两个布阵方式被认为是不同的当且仅当存在一个节点
输入格式
第一行一个正整数
对于每组数据,第一行三个整数
接下来
输出格式
对于每组数据,输出一个数表示该组数据的答案。
样例
input
2 5 4 5 1 2 1 3 1 4 1 5 8 7 2 1 2 2 3 3 4 4 5 5 6 6 7 7 8
output
2 2
explanation
对于第一个数据,五个点形成一个十字路口,根据乘法原理共有
对于第二个数据,构成一个
限制与约定
对全部数据,有
测试点编号 | 备注 | ||
---|---|---|---|
1 ~ 3 | |||
4 ~ 5 | |||
6 | |||
7~10 |
时间限制:
空间限制: