本题没有可用的提交语言。

题目描述

最近，Vasya接触了数学和逻辑学中的一个有趣流派——“直觉主义”。该流派的核心思想是拒绝排中律（即经典逻辑中“任何命题非真即假”的法则）。Vasya深受启发：“经典数学说费马大定理要么成立要么不成立，但在我看到证明或反例之前，这种断言毫无意义。”因此，他成为了一名直觉主义者，并尝试在科研中使用直觉主义逻辑。然而，这种逻辑比经典逻辑复杂得多，Vasya常误用经典逻辑中有效但直觉主义下无效的公式。

现在，他需要编写一个程序来自动验证公式的有效性。他找到了一本相关书籍，但编程能力有限，于是请求您的帮助。

模型构建

1. 基础结构：

   • 给定一个无环有向图$X = (V, E)$，其中$V$为顶点集，$E$为边集。
   • 定义偏序关系：$x \leq y$当且仅当存在从$x$到$y$的路径（路径长度可为$0$）。

2. 集合定义：

   • 设$\mathcal{B}$为$V$的所有子集构成的集合。
   • 定义$\mathcal{H} \subset \mathcal{B}$为$\mathcal{B}$中所有反链（即任意两个元素不可比）的子集，包括空集和单元素集。

3. 运算规则：

   • Max运算：对任意$M \subseteq V$，$Max(M)$表示$M$中所有极大元素的集合。
   • 逻辑运算（对$\alpha, \beta \in \mathcal{H}$）：
     • 合取：$\alpha \land \beta = Max(\alpha \cup \beta)$
     • 析取：$\alpha \lor \beta = Max(\{ x \in V \mid \exists y \in \alpha, z \in \beta : x \leq y \text{且} x \leq z \})$
     • 蕴含：$\alpha \Rightarrow \beta = \{ x \in \beta \mid \nexists y \in \alpha : x \leq y \}$
     • 常量：$0 = Max(V)$，$1 = \emptyset$
     • 否定：$\lnot \alpha = (\alpha \Rightarrow 0)$
     • 等价：$\alpha \equiv \beta = ((\alpha \Rightarrow \beta) \land (\beta \Rightarrow \alpha))$

输入输出

• 输入：
  • 第一行：顶点数$N$和边数$M$。
  • 接下来$M$行：每条边的起点$s_i$和终点$t_i$。
  • 下一行：公式数量$K$。
  • 随后$K$行：每个公式（由0, 1, A–Z, (, ), ~, &, |, =>, =构成，分别表示常量、变量、逻辑运算）。
• 输出：
  • 对每个公式，输出valid（在模型下恒为$1$）或invalid。

示例

输入：

6 6  
1 2  
2 3  
2 4  
3 5  
4 5  
5 6  
11  
1=0  
X|~X  
A=>B=>C = (A&B)=>C  
~~X => X  
X => ~~X  
(X => Y) = (Y | ~X)  
A&(B|C) = A&B|A&C  
(X=>A)&(Y=>A) => X|Y=>A  
X = ~~X  
~X=~~~X  
~X = (X => 0)  

输出：

invalid  
invalid  
valid  
invalid  
valid  
invalid  
valid  
valid  
invalid  
valid  
valid  

来源

Northeastern Europe 2002, Northern Subregion