You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Vlatko 喜欢与整数数组打交道。

他在纸上写下了两个分别包含 $N$ 个元素的数组，其中每个元素是一个整数，或者是表示一个变量的字符串（字符串仅包含小写字母）。

一个变量可以被任何一个整数替换，而两个数组中可能会多次出现同一变量。假如这种情况出现，则替换时需要将该变量出现过所有位置均替换会为待替换整数。

Vlatko 好奇能不能将所有变量替换为特定的整数，使得两个数组相等。当两个数组所有位置处的整数均对应相等，则两个数组相等。

输入格式

第一行输入正整数 $N$，表示每个数组中元素个数。

第二行输入第一个数组的 $N$ 个元素。

第三行输入第二个数组的 $N$ 个元素。

数组中的每个元素为下列二者之一：

• 一个小于 $1000$ 的正整数
• 一个长度不超过 $10$ 的仅包含小写字母的字符串，表示一个变量。

输出格式

如果有方案能在替换后使得两个数组相等，则输出 DA，否则输出 NE。

3
3 1 2
3 1 x

DA

4
4 5 iks ipsilon
1 iks 3 iks

NE

5
x 3 x y 3
x y 2 z 3

DA

提示

样例 3 解释

当把 $x,y,z$ 分别替换为 $2,3,3$ 时，两个数组相等，均为 $(2,3,2,3,3)$。

数据规模与约定

对于 $20\%$ 的数据，每个变量在两个数组中仅出现一次。

对于另外 $20\%$ 的数据，数组中只包含两个变量 $x,y$。

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^4$。

说明

本题分值按 COCI 原题设置，满分 $70$。

题目译自 COCI2018-2019 CONTEST #1 T2 Zamjena。