拯救之路

在忍者的世界里有众多的忍者村，鸣人和佐助出生在木叶村，他们从小一起学习忍术，但是佐助为了获得更强的力量离开了木叶村投奔了邪恶的大蛇丸。鸣人为了不让佐助被邪恶的力量所控制，决定只身前往大蛇丸的根据地拯救他。这里有n个忍者根据地，木叶村位于根据地1，大蛇丸位于根据地n，然后有m条双向的道路连接这n个根据地，每条路有一个特定的长度L。因为大蛇丸忍术高深，所以拯救之路注定不安逸。大蛇丸对每条路都施了一种忍术，每条路都用一个特定的字符标注（‘F’，‘U’，‘C’，‘K’中的一种），因此每条路鸣人只能按照特定的路线走方可到达大蛇丸的巢穴拯救佐助，鸣人走的路线必须是按照以下序列 ‘F’->’U’->’C’->’K’->’F’->’U’->’C’->’K’->.... etc，否则他是达到不了大蛇丸的巢穴的。为了让拯救之路更艰难，大蛇丸又施加了一种忍术，到达大蛇丸根据地时必须是走的完整的一个或者多个“FUCK”序列，这样才能拯救成功。
Note：为了让拯救行动更加容易，应该让拯救路线尽量短，同时应该让“FUCK”序列尽量长。

　　第一行输入一个整数T(1<=T<=500)，表示测试数据的组数。
　　每组测试数据有两个整数n（1<=n<=1500），m（1<=m<=20000），表示n个忍者根据地和m条道路。
　　接下来输入m行，每行有4个变量 “u v L c”，表示这是一条路介于根据地u，v（1<=u，v<=n），这条路的长度是L（1<=L<=1000000），c是一个标记字符（‘F’，‘U’，‘C’，‘K’中的一种）。

如果拯救行动无法完成，请输出Impossible。否则输出拯救路线的长度以及走过的“FUCK”序列个数。

2 
4 4 
1 2 1 F 
2 1 1 U 
1 3 1 C 
3 4 1 K 
4 4 
1 2 1 F 
2 3 1 U
3 4 1 C 
4 1 1 K

4 1
Impossible

Mr.Ant

Close | Top

Administration