3791: 正反硬币森林

John和Ted在玩一种很有趣的游戏。John把一把硬币撒在桌上，然后一个一个拿回来，如果是正面向上则记下‘P’，如果是反面向上则记下‘G’。这样，John就得到了一串P和G的随机序列。这时，他需要按照如下格式作一些申明：“第i个字母是X，或者，第j个字母是Y。”每次申明中的i和j必须不同，X和Y必须是P或G中的一个。而且，申明中的两个判断必须至少对一个。Ted坐在沙发上听John的申明，并且试图从中推断出硬币的真实PG序列。编制一个程序来帮助Ted从John的申明中推断出所有可能的序列，如果序列存在的话。

第一行是序列长度L，2 ≤ L ≤ 1000。第二行是申明次数N，1 ≤ N ≤ 100,000。接下来的各行符合如下格式： i X j Y 。其中1 ≤ i， j ≤ L，i和j必须不同，X和Y必须是P或G中的一个。

输出一个符合要求的序列。如果没有，输出 -1。解不唯一，仅需要求出一种可能的解。

3
6
1 G 2 G
2 G 3 G
1 G 3 G
2 P 3 P
1 G 2 P
1 P 3 G

GPG