#P5076. 「FJSC2018TGD7T3」宝藏
「FJSC2018TGD7T3」宝藏
Description
小E无意间得到了一张藏宝图。顺着藏宝图的指引,小E找到了藏宝洞的入口。
根据藏宝图的描述,藏宝洞中共有个洞穴和条单向通道(单向是因为有一些玄妙的机关),通道有黑白之分,第i条通道由第个洞穴通往第个洞穴,颜色为。通道可能形成重边或自环。藏宝洞的入口在第个洞穴。
入口处有一个石碑,石碑上记录了找到宝藏的方法。石碑上都是些难懂的话语,什么“秩序”“混沌”“周而复始”之类的,不过这难不倒小E,小E马上就破译了石碑给出的信息:
黑白两种颜色可以分别看作和,用以下方式构造一个串:初始串为一个,进行无限多次操作,每次将当前串取反后得到的串接在当前串后,最终得到一个无限长的串。例如,这个串的前几位分别为……
从入口出发,第i步需要走一条与这个串第位相同颜色的通道,尽可能地走最多的步数后到达的洞穴既是宝藏所在之地。
由于藏宝图可能出现破损信息错误或是宝藏本身就是假的,可能出现有多个合法的宝藏所在地或是要无限走下去的情况。小E现在只想知道,根据当前信息,她需要多少步才能找到一个合法的宝藏所在地。如果需要的步数超过,小E可能会弃疗。
Input Format
从 treasure.in
读入数据
第一行包含两个非负整数。
接下来行,每行三个非负整数,分别表示。
Output Format
向 treasure.out
输出数据
输出一个整数,表示答案,如果答案超过,输出。
Sample
样例输入1
2 2
1 2 0
2 2 1
样例输出1
3
样例输入2
2 3
1 2 0
2 2 0
2 2 1
样例输出2
-1
Hint
对于前的数据,答案不超过。
对于前的数据,。
对于的数据,,。