P16115 [USTCPC 2026] Climbing Tree

Today, Kruskal-chan is again staring at the whiteboard in the club room, thinking hard. “Hmm... walking around on a tree, and in the end returning to the starting point... does such a tree really exist?” A junior curiously leans over. “Senpai is studying another weird problem again?” “It’s not weird at all!” Kruskal-chan puffs out her cheeks. “This is the key problem that decides whether I can return to where I started!” She stares at the action sequence in her hand, lightly tapping the desk with her fingers. “If we can find such a tree, it must be very interesting~”

In a rooted tree $R$, the nodes are labeled with distinct positive integers. Kruskal-chan initially stays at some node of $R$. She can perform the following four actions: - Move to the parent node, denoted by `p`. - Move to any child node, denoted by `c`. - Move to any sibling node with a smaller label, denoted by `l`. - Move to any sibling node with a larger label, denoted by `r`. Given an action sequence, determine whether there exists a rooted tree $R$ such that, by appropriately choosing the initial node and the target node of each action, Kruskal-chan can return to the initial node exactly after performing all actions. Note: You should ensure that your construction is valid at every step. For example, if the current node is the root, then you cannot perform action `p`.

**This problem contains multiple test cases.** The first line contains an integer $T$ ($1\le T\le 10^5$), representing the number of test cases. Then $T$ lines follow. Each line contains a non-empty string consisting only of the characters `pclr`, representing the action sequence. It is guaranteed that the total length of all action sequences does not exceed $10^5$.

Output $T$ lines, each representing the result for one test case. If there exists a rooted tree $R$ that satisfies the requirement, output `Yes`, otherwise output `No`.

For the first and the third test cases, it can be proven that it is impossible to return to the initial node in the end. The figure below shows a tree that satisfies the second test case. The root node is labeled $2$, and the initial node is labeled $4$. The action process can be $4\to 1\to 4$ or $4\to 3\to 4$.  The figure below shows a tree that satisfies the fourth test case. The root node is labeled $2$, and the initial node is labeled $1$. The action process is $1\to 4\to 1\to 2\to 1$.  Translated by ChatGPT 5