正反硬币森林

问题描述
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。
解不唯一，仅需要求出一种可能的解。