A relation R on the set {1, 2, ..., n} is given as a list of pairs. Decide which properties it has.
Input
The first line has n and m (1 ≤ n ≤ 10, 0 ≤ m ≤ 100). Each of the next m lines has a pair a b (1 ≤ a, b ≤ n), meaning a R b. A pair may be listed more than once.
Output
Six lines, each ending in yes or no:
reflexive: ...
symmetric: ...
antisymmetric: ...
transitive: ...
equivalence relation: ...
partial order: ...
Examples
Example 1 · Input
3 4 1 1 2 2 3 3 1 2
Expected output
reflexive: yes symmetric: no antisymmetric: yes transitive: yes equivalence relation: no partial order: yes
Example 2 · Input
3 5 1 1 2 2 3 3 1 2 2 1
Expected output
reflexive: yes symmetric: yes antisymmetric: no transitive: yes equivalence relation: yes partial order: no
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep the pairs in a set of tuples, so (a, b) in R is quick.
Hint 2
Each property is an all(...) over elements or pairs, as in the lesson.
Hint 3
Equivalence: reflexive, symmetric and transitive. Partial order: reflexive, antisymmetric and transitive.
Solution
Show one correct solution (try it yourself first)
n, m = map(int, input().split())
R = set()
for _ in range(m):
a, b = map(int, input().split())
R.add((a, b))
A = range(1, n + 1)
reflexive = all((a, a) in R for a in A)
symmetric = all((b, a) in R for (a, b) in R)
antisymmetric = all(a == b for (a, b) in R if (b, a) in R)
transitive = all((a, d) in R for (a, b) in R for (c, d) in R if b == c)
yes = lambda x: "yes" if x else "no"
print("reflexive:", yes(reflexive))
print("symmetric:", yes(symmetric))
print("antisymmetric:", yes(antisymmetric))
print("transitive:", yes(transitive))
print("equivalence relation:", yes(reflexive and symmetric and transitive))
print("partial order:", yes(reflexive and antisymmetric and transitive))