[Question]
  [
You are fighting an extensive network of enemy **spies**. You know that each spy has at least one (sometimes multiple) **fake identities** they like to use. You'd really like to know how many spies you're actually dealing with.
Luckily, your counter-intelligence **agents** are doing their job and can *sometimes* figure out when two fake identities are actually controlled by the same enemy spy.
That is to say:
* Your agents don't always know when two fake identies have the same spy behind them, however
* If an agent tells you two fake identities are controlled by the same spy, you trust they are right.
# Agent messages
Agents send you cryptic messages telling you which identities have the same spy behind them. An example:
You have **2 agents** and **5 fake identities** to deal with.
The first agent sends you a message:
```
Red Red Blue Orange Orange
```
This means they think there are 3 spies:
* the first one (Red) controls identities 1 and 2
* the second one (Blue) controls identity 3
* the third one (Orange) controls identities 4 and 5
The second agent sends you a message:
```
cat dog dog bird fly
```
This means they think there are 4 spies:
* the first one (cat) controls identity 1
* the second one (dog) controls identities 2 and 3
* the third one (bird) controls identity 4
* the fourth one (fly) controls identity 5
Compiling the intel we see:
```
Identities:   id1    id2    id3    id4    id5 
Agent 1:    |--same-spy--|       |--same-spy--|
Agent 2:           |--same-spy--|
Conclusion: |-----same-spy------||--same-spy--|
```
This means there are at most **2 spies**.
# Notes
Identities owned by the same spy do not have to be consecutive, i.e. a message like:
```
dog cat dog
```
is valid.
Also, the same word might be used by two different agents - that does not mean anything, it's just a coincidence, e.g.:
```
Agent 1: Steam Water Ice
Agent 2: Ice Ice Baby
```
Ice is used by both agents - the `Ice` used by the first agent is unrelated to the two occurences of `Ice` used by the second agent.
# Challenge
Compile all your agents' intel and figure out how many enemy spies there really are. (To be more precise, get the lowest upper bound, given the limited information you have.)
The shortest code in bytes wins.
# Input and Output spec
The input is a list of n lines, which represent n messages from agents.
Each line consists of k space-separated tokens, same k for all lines. Tokens are alphanumeric, arbitrary length. Case matters.
The output should be a single number, representing the number of distinct spies, based on your agents' intel.
# Examples
### Example 1
Input:
```
Angel Devil Angel Joker Thief Thief
Ra Ra Ras Pu Ti N
say sea c c see cee
```
Output:
```
2
```
### Example 2
Input:
```
Blossom Bubbles Buttercup
Ed Edd Eddy
```
Output:
```
3
```
### Example 3
Input:
```
Botswana Botswana Botswana
Left Middle Right
```
Output:
```
1
```
### Example 4
Input:
```
Black White
White Black
```
Output:
```
2
```
### Example 5
Input:
```
Foo Bar Foo
Foo Bar Bar
```
Output:
```
1
```
### Example 6
Input:
```
A B C D
A A C D
A B C C
A B B D
```
Output:
```
1
```
### Example 7
Input:
```
A B A C
```
Output:
```
3
```
### Example 8
Input:
```
A
B
C
```
Output:
```
1
```
### Example 9
Input:
```
X
```
Output:
```
1
```
  
[Answer]
# [Sledgehammer 0.5.1](https://github.com/tkwa/Sledgehammer/commit/9e4f8257aae28f8aa0660948d2141e2745c15100), ~~16~~ 15 bytes
```
⡡⠥⡀⡾⠥⢢⠍⣽⡷⣩⣅⡷⣡⢒⠅
```
Decompresses into this Wolfram Language function (the final `&` is implicit): 
```
Length[ConnectedComponents[RelationGraph[Inner[Equal, ##1, Or] &,
    Transpose[StringSplit @ #1]]]] &
```
[Try it online!](https://tio.run/##JY1BasMwEEX3PsVHBq@0yQG6KGkpCaEJjnfCi8Ed2yLyyJHk4lJ6dldtZobPXzzmTZRGnijZjratxxNOLEMazd6LcJf4Y@@n2QtLiqYAanaZ9fIWaB7NITPBvN4XchpludM4hxaVRibRBJI4@8jmmoKV4To7m0y5a/@m2tbs@lbPMrDDC39ah0c/@hsHNKPl/pEqv1M14f8iLgsai3elCxXpC5EJXd7IjI5Z/RSXLEumN2vbbr8 "Wolfram Language (Mathematica) – Try It Online")
`Transpose[StringSplit @ #1]`: Split each string in the input list, and take the columns (spy identities)
`RelationGraph[Inner[Equal, ##1, Or] &, ...]`: Construct the graph where two vertices share an edge if at least one position is equal (if they are classified as the same spy by some friendly agent)
`Length[ConnectedComponents[...]]`: The number of connected components is the upper bound on the possible number of spies.
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), ~~155 150 142~~ 141 bytes
```
a=>new Set((a=a.map(s=>s.split` `))[0].map((_,x)=>a.flat(m=1<<x).map(o=_=>a.map((b,y)=>b.map((w,i)=>m>>i&1|o[w+=y]?o[w]=m|=1<<i:0)))|m)).size
```
[Try it online!](https://tio.run/##fU5bT8IwFH7frzhPssa5wKuhMwzwwagxSKIJIdBtZ1Dp1mUtjBn@@yxrjCbK0ss557u1H@zAVFzyQt/kMsEmpQ2jQY4VvKJ2XUaZn7HCVTRQvioE12tYE7LoL1vYXXlHQgPmp4JpN6OD4fBIWkbS1RlvRZFXG1Fkh8rjZsiCgF8NTnJRXdN6eWfqkmans5/f9gkhp4wQX/FPbGKZKynQF3Ljpu7CAeiN8g0KmOCBC7D9g9xhCfMtx9TePe8snDFot4KXPcw5PFtYsRoUMojNUogQI/acJSGO889joZBKyQzCfRQJVKZqjWW8L2zWNIFp0p66I0NqVbGcwZ/GhjxiquGJJ4lAmPHNVnd9h8U7eNtyjdbbttDCl133UkLISjDVur4Bcy67RhDCGCbWMYLR7@HMjH@G0DCdOcbcIbBBoS0dwveWar4A "JavaScript (Node.js) – Try It Online")
### How?
For each column \$x\$, we build a bitmask \$m\$ of linked columns (including the \$x\$th column). We eventually return the number of distinct bitmasks.
```
+---------+-------+-------+-------+-------+-------+-------+
| x       |   0   |   1   |   2   |   3   |   4   |   5   |
+---------+-------+-------+-------+-------+-------+-------+
| 2**x    |   1   |   2   |   4   |   8   |  16   |  32   |
+---------+-------+-------+-------+-------+-------+-------+
| words   | Angel | Devil | Angel | Joker | Thief | Thief |
|         | Ra    | Ra    | Ras   | Pu    | Ti    | N     |
|         | say   | sea   | c     | c     | see   | cee   |
+---------+-------+-------+-------+-------+-------+-------+
| bitmask |  15   |  15   |  15   |  15   |  48   |  48   |
+---------+-------+-------+-------+-------+-------+-------+
```
### Commented
```
a =>                      // a[] = input
new Set(                  // we eventually convert the generated array into a set
  (a = a.map(s =>         // we first need to convert each line into
    s.split` `            // an array of words (*sigh*)
  ))                      //
  [0].map((_, x) =>       // for each word at position x in the first line:
    a.flat(m = 1 << x)    //   initialize a bitmask m with the x-th bit set and build an
                          //   array containing as many entries (N) as there are words in
                          //   the whole matrix
    .map(o =              //   the object o is used to store words
         _ =>             //   repeat N times to ensure that all relations are found:
      a.map((b, y) =>     //     for each line b[] at position y in a[]:
        b.map((w, i) =>   //       for each word w at position i in b[]:
          m >> i & 1 |    //         if the i-th bit is set in m (the relation already
                          //         exists)
          o[w += y] ?     //         or w + y is set in o (a relation exists in this line):
            o[w] =        //           set o[w + y] (the value doesn't matter as long as
                          //           it's non-zero)
              m |= 1 << i //           set the i-th bit in m
          :               //         else:
            0             //           do nothing
        )                 //       end of map() over the words
      )                   //     end of map() over the lines
    ) | m                 //   end of map() over all flatten entries; yield m
  )                       // end of map() over x
).size                    // return the size of the corresponding set
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 19 bytes
```
ḲiⱮ`)ZŒc€ẎyⱮ@ƒƊÐLQL
```
[Try it online!](https://tio.run/##y0rNyan8///hjk2ZjzauS9CMOjop@VHTmoe7@iqBfIdjk451HZ7gE@jz/@HuLYfb//93zEtPzVFwSS3LzFGAsL3ys1OLFEIyMlPTICRXUKICGBUrBJQqhGQq@HEVJ1YqFKcmKiQDYXFqqkJyaioA "Jelly – Try It Online")
Takes input as a list of space-separated lines (the footer accounts for that).
Note: `ḲŒQ)PS` does **not** work.
[Answer]
# [Python 3](https://docs.python.org/3/), ~~132~~ ~~162~~ ~~154~~ ~~139~~ 135 bytes
```
def f(a):r=[*zip(*[map(b.index,b)for b in map(str.split,a)])];return sum(i==min(min(u)for u in r if min(w)in u)for i,w in enumerate(r))
```
[Try it online!](https://tio.run/##ZZBPa9wwEMXv/hSPXCwHN9DmtsWFOJseQlpKCPRgfJDt8a6ILRv96Wa77GffarRxEwjS2E9P85sRM@/ddtLXp1NHPXohs5Upqsu/ahaX1Shn0Vwp3dFL3mT9ZNBAabBtnbmy86BcLrM6q78act5oWD8KVRSj0oLDR8gzZKB6sLfLwul8ofIdX5H2IxnpSJgsO7XSkkWBKoGo0hu9oQFr@qMGnPX99EwGT1sV3hu/aY70USJui18eTwo/2bRyD0sSbViWCC1RWuf4kuWxdDlM1k4jSt80Q2hZeufItH5m9q7DXRdjz8z1wkzO7qSW@CAYeqDe4YfquoHwqDZbx@jn/@1k@4zfW@WIc6NANN8/6vs0oZQG4c9ZyzHE@1o3KHGLNWewXC/ydnHL14TIJKiThOfNo81BLzO1jjoefRz2KoFsnZdDmHov2ArIbJR2or84VGkv1UBdmqeztDaIujqnF8VSqj6ucGDwiE/f3hocFnXMsZkcDmfueJGd/gE "Python 3 – Try It Online")
This is a very compact implementation of a graph algorithm identifying clusters.
1. For each agent, we create a map of profiles and their alias, which is the lowest index of appearance: `[map(b.index,b)for b in map(str.split,a)]`. I.e. `[0,1,2,1,2]` identifies three spies, where the first profile belongs to one, the second and fourth to another one and the third and fifth to the last one. The group index is also the index of the first profile in the group.
2. By transposing this matrix (`[*zip(*m...)]`), we get a group membership for each profile. This forms a directed, acyclic graph, because the group indices are a subset of the profile indices, and all edges go towards lower or equal indices. Profiles corresponding to the same spy now form a cluster with no connections to the other profiles. We still have duplicate paths though, because profile indices are linked to multiple groups indices.
3. With the following loops, we minimize the the graph to a flat forest, where all profiles are linked directly to the lowest index in their tree, i.e. the root: `min(min(u)for u in r if min(w)in u)`
4. Finally, return the number of roots in the forest, i.e. indices linked to themselves: `return sum(i==...)`.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~49~~ 43 bytes
```
≔⪪Ｓ θＷＳ«≔⪪ι ιＦＬιＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»ＩＬΦθ⁼κ⌕θι
```
[Try it online!](https://tio.run/##VY9RbsIwDIafySksnhypOwFPiA2JaZvQ6AWsYlqrJm2TlA1NO3uXFtDUOLLi@P/yO0VFvmhIh2EdgpQOD61KxJ1r@3iIXlyJNoMlLFPu7Mp8VaIM876FH7OY4fJAJCGLU@MB39iVsUJJ6ndqN835TO6IXQY5e0f@ii9dTxpQM1jHnTvy99isrZ3VW0mQ/F/JJEkatcnp1@zTRBE3FOLDcCsa2Y/s3aC@v9KN001rlT7vSlZ45oso3M6vTc0e8kr4dMvmk2DaAfY95AIfJtAVAhMUKQIzFMxmeLroHw "Charcoal – Try It Online") Link is to verbose version of code. Could possibly save a couple of bytes by using a cumbersome input format. Explanation:
```
≔⪪Ｓ θ
```
Input the first agent's list.
```
ＷＳ«
```
Repeat for the remaining agents.
```
≔⪪ι ι
```
Input their list.
```
ＦＬι
```
Loop over each element index.
```
ＵＭθ⎇⁼λ§θκ§θ⌕ι§ικλ»
```
Find the first element in this agent's list with the same identity and update the first agent's list to show that they are the same identity.
```
ＩＬΦθ⁼κ⌕θι
```
Count the number of unique identities remaining.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~25~~ 15 bytes
```
ḲĠ)ẎfƇFQɗⱮQ$ÐLL
```
[Try it online!](https://tio.run/##y0rNyan8///hjk1HFmg@3NWXdqzdLfDk9Ecb1wWqHJ7g4/P/4e4th9u5rB81zDm0TddO4VHDXOvD7daPGrdzHZ38cOfiR437Dm07tO1w@6OmNZH//zvmpafmKLiklmXmKEDYXvnZqUUKIRmZqWkQkisoUQGMihUCShVCMhX8uIoTKxWKUxMVkoGwODVVITk1lYvLKSe/uDg/V8GpNCkpJ7UYSJeUpBYllxZwuaYouKaAcSVQWX5JcXliXqICBoPLJzWtRME3MyUlJ1UhKDM9owRkaGJytkJ4RmZJKheYVACLcHE5KjgpOCu4AGlHKA3iO4NpJwUXAA "Jelly – Try It Online")
A monadic link taking a list of space-separates agent claims and returning the lowest upper bound of the number of distinct spies. 
## Explanation
```
  )              | For each list:
Ḳ                | - Split at spaces
 Ġ               | - Group indices of equal items
   Ẏ             | Tighten lists, so we have a single list of grouped indices
           $ÐL   | Repeat the following until no change:
        ʋⱮQ      | - Do the following as a dyad, mapping through each element of the uniquified list as the right argument
    fƇ           |   - Keep only those list members with one or more items matching the right argument
      F          |   - Flatten
       Q         |   - Uniquify
              L  | Finally take the length of the resultant list
```
Thanks to @Arnauld and @JonathanAllan for identifying issues with previous versions, and to @JonathanAllan again for saving a byte! If the input spec were relaxed to allow a list of lists, this would save one byte. 
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 120 bytes
```
a=>a.map(l=>(s=l.split` `).map((w,i)=>r[o(i)]=o(s.indexOf(w)),o=i=>r[i]-i?o(r[i]):i),r=[])|r.map(g=(v,i)=>t+=v==i,t=0)|t
```
[Try it online!](https://tio.run/##fU5da8IwFH3vr7hvJqyWPQ/iaNU9jH0hwh6kYGxv652xKUmsE/zvXdswNtiU5Oaee07OST5kI21mqHbjSufYFqKVYiKjvayZEhNmhYpsrcitYc0Hlh1D4mJiVpoRT4VmNqIqx8/Xgh05D7WgXqR0TPea9YDfEQ@NWKX8bIaEUrBmyHA3ohGCQidu@dm1ma6sVhgpXbKCrQKAUVyVqGCGDSnw@FHv0MByS1j4cxT2FxcShm3h7QBLghdPW3kCixKybllEyBBHQcp5EPzzWKK0tXoPyWGzUWi77hya7FD7rHkO83yo05UM7exRVhL@AB/yhIWDZ8pzhbCgcuuufUdmO3jfkkPvHSAM9GXXg9aQSANd965voqvLrhgSmMLMO2KIfw@9Mv0Zkk7pc9ov "JavaScript (Node.js) – Try It Online")
```
a=>a.map(l=>(                  // for each line
  (s=l.split` `).map((w,i)=>(  // for each words in line
    r[o(i)]=o(s.indexOf(w)),   // join(current index, first occurrence index)
  )),                          //   without updating nodes in path
  o=i=>r[i]-i?o(r[i]):i,       // a function to find root of some node
  r=[]                         // initial disjoint-set
))|
r.map(g=(v,i)=>t+=v==i,t=0)|   // count roots of tree
t                              // output
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 12 bytes
```
LωomΣknṁoηkw
```
[Try it online!](https://tio.run/##yygtzv7/3@d8Z37uucXZeQ93Nuaf255d/v///2glx7z01BwFl9SyzBwFCNsrPzu1SCEkIzM1DUIq6SgFJSqAUbFCQKlCSKaCH1CsOLFSoTg1USEZCItTUxWSU1OVYgE "Husk – Try It Online")
## Explanation
The idea is to create a list of all groups of spies that are known to be the same person, then progressively merge intersecting groups until a fixed point is reached.
The output is the number of remaining groups that couldn't be merged.
```
LωomΣknṁoηkw  Implicit input: list of strings, say ["a bc a","b g g"]
       ṁ      Map and concatenate:
           w   Split at spaces: "a bc a" becomes ["a","bc","a"]
         ηk    Group indices by equality of elements: [[1,3],[2]]
              Result: [[1,3],[2],[1],[2,3]]
 ω            Iterate until result doesn't change:
     k         Group greedily by
      n        (non-emptiness of) intersection: [[[1,3],[1]],[[2],[2,3]]]
   mΣ          Concatenate each part: [[1,3,1],[2,2,3]]
              Result: [[1,3,1,2,2,3]]
L             Length: 1
```
[Answer]
# [Python 3](https://docs.python.org/3/), ~~191~~ 182 bytes
### Thank you recursive
```
e=enumerate
def f(a):
	r=[list(map(b.index,b))for b in map(str.split,a)]
	for z in r:
		for i,v in e(z):
			for x in(i>v)*r:x[(i,x[i])[x[i]<i]]=z[v]
	return sum(i==v for i,v in e(z))
```
[Try it online!](https://tio.run/##ZVJNb6MwED0nv@L1hF2hSm1v1bJS6MehaqtVVWkPiIMJQzOqA8g2NMmfz3pIolZdwPabN/OeYUy/Dauuvd7vKaN2WJMzgeY1NWiU0TfzmcsKyz6otelVdcFtTZu00rrpHCpwC@F9cBe@txxSo8v5THI7ybmonyJOR4lJ7cTywG0io/j3qM/dzaZQnG4KLnUh8y8uy2xXjNHLURhcCz@sFWfZiB9uei9EIB9SOPKDDZIpVJEs2neyuKORLQ74sfsgh7cVx4@b5iRF8mowPR5/BrwxXoT0ZgtPBst4eyIsiZIyxZVOEZ1z23nfrZEPVWXJxzUEcsuhF@l9jft6GluRXB8lXfCfpjX4D4jmiZqAZ65rS3jl91UQ5eVpM7P8wN8VB5LSCWAiv73RQ9chNw5xlaJTGMc3pwVy3OJOChZYfEFhb08wj@wkKeM5sfwE0luNLDu2V46vd9wGdWh60hvvqU70fEbW01c6OftxxS2OksawFcn@Hw "Python 3 – Try It Online")
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~123~~ 117 bytes
Uses a similar idea to [movatica's Python 3 solution](https://codegolf.stackexchange.com/a/188349/52194) but calculates the lowest spy index for each "tree" in a slightly different way (by keeping track of previous encountered profiles, finding an overlap if it exists, and combining them)
-6 bytes from @GB.
```
->a,*b{a.map{|s|e=s.split;e.map{|i|e.index i}}.transpose.map{|e|b<<(b.find{|i|i-e!=i}||[])+e}
b.map(&:min).uniq.size}
```
[Try it online!](https://tio.run/##JY7RagIxEEXf8xUjlLJraz6gbgqCT30oIr6JlGS9q0NjTM1uu2ry7Vs13GEYzpyHe@rMeWjUMHnXr2Nz7ZWWB@2vMUSoIIO33E6REUdIdlv0xCmJXvqjlxf2xbgvs4BoqqowsrlZd50nGClOMa435QuSMHeteH47sCtl5/hHBr4gDex816r1Rvzt2YJ2aIOgB6SqoqevXEPAbYXw1MhaW5v/w8ztYGmOX7aU74/jN0602jOavMVS02MCLTpaMX2KoM8UoKm@JQBUA/8 "Ruby – Try It Online")
### Explanation
```
->a,*b{                                             # Start lambda with input a, b=[]
       x=
         a.map{|s|                             }    # For each agent's report
                  e=s.split;                        # Split the words
                            e.map{|i|e.index i}     # Get spy number for each
   .transpose                                       # Transpose to get group membership
             .map{|e|                            }  # For each profile
                        (b.find{|i|i-e!=i}||[])     # Find a profile in b that overlaps
                                                    #  If one is not found, use []
                                               +e   # Add the profile onto the found one
                     b<<                            # Insert this modified profile into b
b.map(&:min)                                        # Get minimum of each modded profile
            .uniq                                   # Deduplicate
                 .size                              # Size of array
}                                                   # Implicit return
```
[Answer]
# [Python 2](https://docs.python.org/2/), ~~229~~ 221 bytes
```
e=enumerate
def f(s):
 v=[];u=sum([(lambda a:[{i for i,x in e(a)if x==k}for k in set(a)])(a.split())for a in s.split('\n')],v)
 while u:
	x=u.pop()
	for i,y in e(u):
	 if x&y:u.pop(i);u+=[x|y];break
	else:v+=[x]
 return v
```
[Try it online!](https://tio.run/##TY9Ba4QwEIXPzq@YU03osrAelRwKPfVQStmb9ZDdHddgjJIYq7T97TbRHkqGYfhemDdvWMamN9m6kiDjO7JyJLhRjTVzPAecRFkVXjjfsZJp2V1uEmVefimse4vqMKMySExyVeMsRPsTcRuhozHgijN5dINWI@M8anLT/lD6YVJeHSYO@NkoTehzSGbhj0M/MA7J7rHsHj7ck2D0eVjy/YvihX8U5fy9VMXFkmwhIe0onyKsAC2N3hqc1sEqM4ZMaZo@mTtpfKZJadznl74li@dGhdhbh3eJWzl883hW@ApOLiGRxGt4jgivRGEXB/i3@YQZniD2LGrrLw "Python 2 – Try It Online")
8 bytes thx to [wilkben](https://codegolf.stackexchange.com/users/88089/wilkben).
[Answer]
# [Clean](https://github.com/Ourous/curated-clean-linux), 137 bytes
```
import StdEnv,Text,Data.List
q=length
$l=q(iter(q l)(map flatten o groupBy isAnyMember)(transpose[[(s,n)\\s<-split" "z]\\z<-l&n<-[1..]]))
```
[Try it online!](https://tio.run/##ZVLRbpswFH1OvuIIVZORIFK31/AQmlTalG5VGmkPwIMDN8SqsYltutGPH3NA6dRV@PoeH93jY@NbSuJqaHTVSULDhRpE02rj8OSqjXqJ9vTbRWvu@GIrrJufE0mqdqf5jUzOTDgy7AwZsoa3OEruHClo1EZ3bdpD2JXqH6g5kAmZM1zZVlvKMmYjFea5Xca2lcIFCF6LPH9dxvKTWsbZ7WJRFGE4PDnuD5KAqwoZuJRgLElCeLomF2J0vQFryTSd405oZSFU27kwRJ6DjTh6q1/GyOazGcuClapJYk0vQmLC3/QzGexPgo7THETBjmMcFo8d9gLfPWd5D0scpf8sEUqioIjwOYymnXdU4RKp7Ag//JXra/LikjtUuh7jIEzlf1n/Tr1Cijusgwgerv7BC3t3halnvej2KkqltlY3SLvDQZL12T@DKbvWO24qbKoxRqMvbxrt7C@uOD6Ai8uWjg4Poqp8T@xEfXL/@fHyGT9P/vUvxSPASL67y73WSLmBz5ey69LHtNt8VhTDn9J3TW2H@Ot2WPeKN6KcFo@@mY7aNH8B "Clean – Try It Online")
Associates the strings used by the agents with the line-number the appear in to prevent equality across agents, then repeatedly checks if any phrases for any position overlap and counts the number of resulting sets.
[Answer]
# [PHP](https://php.net/), 271 bytes
This won't work if any of the identities are just numbers as I store the "spy number" in with the identities. I don't think it wouldn't be hard to fix that though.
```
$a=$argv;array_shift($a);if(count($a)==1)array_push($a,...$a);foreach($a as&$b)$b=explode(" ",$b);$c=array_map(null,...$a);foreach($c as&$d)foreach($d as$k=>$e){if(!$d[s])$d[s]=++$s;foreach($c as&$f)if($f[$k]==$e)$f[s]=$d[s];}echo count(array_unique(array_column($c,s)));
```
[Try it online!](https://tio.run/##ZY/BSgMxEIbvPsVYgmzouuB5jSJ48qAivZVS0uxkEzZNYrIpFvHVjemueKhMGGb@@b9h4pXPt/eZcEZ46A8tD4Eft1FpOVaE01bLSrhkp4axGzrPfYqqKHXTNCeTdAG5OCnA4xXZUbJj@OGN67BawKIuSksEm9k995VNxvyDxQR39E/oikAGdkeQfpY7Lkm3jhs6ZbZckniOSlpcRK7JsGGsQKUszsnffqFQDuavzHckq98T/jbCmbS3ZVEdKaVtzhf5wfZo4BEP2sBcP7kBA6yURjnn/MZhehFeE6w0POfIjxCRgygREUEgfjs/amdjvu6icmHcOo92O/Kevdgf "PHP – Try It Online")
### Explanation
Sort of confused myself writing this but it works for all the test cases!
```
$a=$argv;					//shorten the arguments variable
array_shift($a);				//removes the script name from the arguments variable
if(count($a)==1)array_push($a,...$a);		//the code needs at least 2 messages to run so if only 1 message duplicate it. "..." passes the stuff in the array rather than the array itself?
foreach($a as&$b)$b=explode(" ",$b);		//turns each string message into an array
$c=array_map(null,...$a);			//if you give array_map "null" for the callabck then it zips the arrays, turning a m by n 2D array into a n by m 2D array. this changes it from the messages being grouped to the identities being grouped
foreach($c as&$d)				//loop over the groups of identities
	foreach($d as$k=>$e)			//loop over the names the agents gave the identity and keep track of the key
	{
		if(!$d[s])$d[s]=++$s;		//if this identity doesn't have a "spy number" give it the next one
		foreach($c as&$f)		//loop over the groups of identities again
			if($f[$k]==$e)		//check if the agents gave any other identities this name 
				$f[s]=$d[s];	//if they did then give those the same "spy number"
	}
echo count(array_unique(array_column($c,s)));	//use array_column to get the "spy number" of each identity, remove duplicates using array_unique and then count the size of the array giving the upper limit of spies
```
[Try it online!](https://tio.run/##jVTRbtMwFH1uvuISRbBopdX2WsKEtCceAKG9TdPkJjeJ1cQ2vna1DvHrlGu7acsAibaq2mvf43POPY7pzf7dzb4QVSFst13Nwmu5pF5bhwpcj8B1P6JyBFthpVgPmAlrxe6Retm6i0KUq9RkcdRbpNhEtZXGgRIjQmv1@C8k2V7U2qsIU1VXZUI2nnquzBeLRYJfLkN/rRsEhdgQCAcDCnJwDSMSiS6cq8F6BaRBtqDVsIOraREabwZZC4cg3QJyBs7BCKKJrvNtC3ISzBzACv5tuSDOq9IRDu1N1mqLog4kQdDrYl0W6wqfzMAML3LI51xJtL1VBGErn2Gl6o6MpGK@jB1xs6KukvRRmAvlh@GknVFYz0576OT2wCNsgzzsy4GpRIK1GAaxrjfhj2Ki8CwNnajTHAKZQEHACOsdKLi@nWRFMlzh8ngsL7hbEtRsQfCXIY@jPJq@xoDYWe0NNmEEYVU2PGXp5Mv1k211tK0pU3IGrQ1wdpKQuJlAt2c42ezY2nBrsaneF1j@pTkk7qC6i1HrBJt2RmrHpjewQTTgrGC7@JywvMFdNvuezWYcyVdFc08PZfyuLi8LWh2mEP04AjUaSb1x0IcjBORk2FQ/rtHmaVbsWOSET44DiQz@woC2/D/5LEZIxf2BXdHeF5uHqooGLJd1j6xCtn@IFmoHOob4DCgqiNcyoM0YiyVGoatJIrIy2aQYRRmu15Q8pNB4rjOb/ciw7jWkW5zC6ZX85vHwp9aDHxULnlNZluEQT1OK01pITYfJqt88ZAvizZkMn0N6xJxuM4GnmOizc@N8I/nIKfGWzzgNOiWehYXGUPDGsEeDHHlcvIcM@7TfZ/sPnPoBbnErB0i/P@oN77zrJbbpe/9VQPwQfPFwJ@HTnhicUEDNb0K@log/tXFSK9q/beKD9VEbVI9OdNVn9Qs "PHP – Try It Online")
]