QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Hackable ✓
[-1]
统计

面国是一个古老而又广阔的国家,菲斯雷斯·杨是这个国家的统治者,面民们称之为面皇。面国由 N 个城市组成,城市按照 1..N 编号,其中 1 号城市是面国里最有面子的城市,所以面皇设定其为面国的首都,我们称之为面都。

在面皇开天辟地的时候,这个世界上是没有道路的,唯一用来连接城市的是面皇的面子:对于任何 i[2,N]1 号城市到 i 号城市都有一条长度为 260 的单向道路,所以从面都出发,到达任何一个普通城市都需要 260 单位的时间。

然而在面国进入工业时代后,面国的居民开始发现靠面子来进行交通是非常低效的,于是面皇开始计划在面国修建一些单向道路,并将这个项目交给了建设大臣艾莉芬特来干。

每条道路可以用一个四元组 (u,v,w,id) 表示,表示一条从城市 u 到城市 v,长度为 w ,修建的时间为 id 的单向道路,因为面国工程能力不足,所以所有道路的修建时间都是互不相同的。

道路修建完之后,面皇会进行视察,由于是面皇亲自视察,所以这个过程非常讲究,所以是非常复杂的,你可以结合下发的 spj.cpp 来理解这一过程。

面皇手中有一张计划表 S,计划表上记录了若干个城市,面皇会按照计划表的顺序从头到尾去视察城市,一开始计划表上只有面都,即 1 号城市。

并且面皇对于每个城市 i 会记录一个值 disi,表示当前在面皇的印象中从 1 号城市出发,到达城市 i 的最短路。一开始 dis1=0,而且由于面皇可以用面子进行交通,所以对于除了面都以外的城市 i,一开始有disi=260

当面皇视察城市 x 时,面皇会按照修建时间从小到大遍历所有以 x 为起点的边 (x,y,w),并且检查城市 y 的最短路是否可以更新,如果可以更新(即 disy>disx+w),那么面皇会令 disy=w+disx,并且检查一下根据计划表后面还会不会视察城市 y,如果暂时视察不到的话,就将城市 y 加入计划表的末尾。

(在另一个世界中,这种视察方法被称为 SPFA。)

然而面皇的爸爸"鸭子的王"曾经说过:"关于SPFA,他已经死了",所以面皇对SPFA感到非常忌讳,于是面皇命令艾莉芬特代替他去视察,并把最后产生的计划表交上来。

然而艾莉芬特也有事情要做,于是他随便造了一张计划表上去,现在面皇想拜托你确认下,是否存在任何一种道路的建设方法,使得最后的计划表跟艾莉芬特交上来的相同

输入格式

第一行两个正整数 NK,分别表示城市个数和艾莉芬特提交的计划表的长度。

第二行 K 个正整数,按照从头到尾的顺序给出了计划表的内容。

输出格式

如果不存在一种道路建设的方法,使得最后的计划表和艾莉芬特给出的相同,则在第一行输出字符串"YouAreFake!" (不含双引号,注意大小写),否则在第一行输出字符串"YouAreWrite!" (不含双引号,注意大小写)。

如果存在一种道路建设的方法满足条件的话,你需要按以下格式输出任意一种方案:

在第二行输出一个整数 M,表示道路的个数 接下来 M 行,按修建时间从小到大的顺序输出道路,每行三个整数 u,v,w 表示从 uv 的长度为 w 的道路。

你构造的方案必须满足:0MK+15,且 0w260

样例数据

样例输入

4 6
1 3 2 4 3 4

样例输出

YouAreWrite!
4
1 3 3
1 2 1
2 3 1
3 4 2

子任务

Task1 (7分):1N3

Task2 (8分):保证在计划表中的数两两不同。

Task3 (9分):保证最多有一个数在计划表中出现超过 1 次。

Task4 (23分):保证计划表中每个数最多出现 2 次。

Task5 (53分):没有限制

对于所有数据,满足 1N1001K104,计划表中的每个数都是 [1,N] 中的整数。