描述

给出一个由0和1组成的串,0代表非叶节点,1代表叶节点,请问这是否能作为是一棵树的DFS序,BFS序(同样,序中的非叶节点用0表示,叶节点用1表示)

输入格式

一行,一个由0和1组成的串,中间没有空格。

输出格式

如果既不能是DFS序,也不能是BFS序,则输出0

如果不能是DFS序,但可以是BFS序,则输出1

如果可以是DFS序,但不能是BFS序,则输出2

如果既可以是DFS序,也可以是BFS序,则输出3

样例输入

0101

样例输出

3

数据范围与约定

  • 对于100%的数据:1<=串的长度<=50

样例解释

    o

  /   \

o       o

             \

                o

这棵树的DFS序和BFS序都是0101

来源

原创