How to find two elements with the maximum number of common links?

Question

MySQL

Hello everyone, I got a problem on the interview, there are three tables: teacher (id, name), student (id, name) and teacher_student (teacher_id, student_id). Moreover, without a composite index on the link table, i.e. any teacher can have any set of students and vice versa.
You need to output two teachers with the maximum number of common students. I broke my whole brain, I was able to cope with all the tasks, but on this one there was a dullness and nothing. Tell me which way to dig? It seems to me that this is impossible.)

Answer 1

SELECT `t1`.`name`, `t2`.`name`, COUNT(*) AS `count`
  FROM `teacher` AS `t1`
  JOIN (
    SELECT DISTINCT `teacher_id`, `student_id`
      FROM `teacher_student` 
  ) AS `s1` ON `s`.`teacher_id` = `t1`.`id`
  JOIN (
    SELECT DISTINCT `teacher_id`, `student_id`
      FROM `teacher_student` 
  ) AS `s2` ON `s2`.`student_id` = `s1`.`student_id` AND `s2`.`teacher_id` > `s1`.`teacher_id`
  JOIN `teacher` AS `t2` ON `t2`.`id` = `s2`.`teacher_id`
  GROUP BY `t1`.`id`, `t2`.`id`
  ORDER BY `count`
  LIMIT 1

Answer 2

something like this
SELECT t.*, count( ts.teacher_id) as c
FROM teacher t
INNER JOIN teacher_student ts ON t.id= ts.teacher_id
GROUP BY t.id
ORDER BY c DESC
LIMIT 2

Answer 3

If I correctly understood the whole joke in the
maximum number of total students
then:
select ts1.teacher_id,ts2.teacher_id, count(ts1.student_id) as cnt
from teacher_student ts1
left join teacher_student ts2
on ts1.teacher_id<>ts2.teacher_id and ts1 .student_id=ts2.student_id
group by ts1.teacher_id,ts2.teacher_id
order by cnt
limit 2