### 问题描述 在忍者的世界里有众多的忍者村，鸣人和佐助出生在木叶村，他们从小一起学习忍术，但是佐助为了获得更强的力量离开了木叶村投奔了邪恶的大蛇丸。 鸣人为了不让佐助被邪恶的力量所控制，决定只身前往大蛇丸的根据地拯救他。 这里有 $n$ 个忍者根据地，木叶村位于根据地 $1$，大蛇丸位于根据地 $n$，然后有 $m$ 条双向的道路连接这 $n$ 个根据地，每条路有一个特定的长度 $L$。因为大蛇丸忍术高深，所以拯救之路注定不安逸。 大蛇丸对每条路都施了一种忍术，每条路都用一个特定的字符标注（L，U，C，K中的一种），因此每条路鸣人只能按照特定的路线走方可到达大蛇丸的巢穴拯救佐助，鸣人走的路线必须是按照以下序列 $L->U->C->K->L->U->C->K->.... $，否则他是达到不了大蛇丸的巢穴的。 为了让拯救之路更艰难，大蛇丸又施加了一种忍术，到达大蛇丸根据地时必须是走的完整的一个或者多个 LUCK 序列，这样才能拯救成功。 Note：为了让拯救行动更加容易，应该让拯救路线尽量短，同时应该让 LUCK 序列尽量长。 ### 输入格式 第一行输入一个整数 $T(1\le T\le 50)$，表示测试数据的组数，每组测试数据有两个整数 $n(1\le n \le 1500)$，$m(1\le m\le 20000)$，表示 $n$ 个忍者根据地和 $m$ 条道路。 接下来输入 $m$ 行，每行有 $4$ 个变量 $u\ v\ L\ c$，表示这是一条路介于根据地 $u,v(1\le u,v\le n)$，这条路的长度是 $L(1\le L\le 10^6)$，$c$ 是一个标记字符（L，U，C，K中的一种）。 ### 输出格式 如果拯救行动无法完成，请输出 Impossible，否则输出拯救路线的长度以及走过的 LUCK 序列个数。 ### 输入样例 ```txt 2 4 4 1 2 1 L 2 1 1 U 1 3 1 C 3 4 1 K 4 4 1 2 1 L 2 3 1 U 3 4 1 C 4 1 1 K ``` ### 输出样例 ```txt 4 1 Impossible ```