diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
index eeb162f..2659562 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/AbstractClassEntryState.java
@@ -55,12 +55,13 @@
 
   public abstract Optional<ClassInfo> classInfo();
 
+  public abstract boolean direct();
+
   /** A state to indicate that a class exists. */
   @AutoValue
   public abstract static class ExistingState extends AbstractClassEntryState {
-
-    public static ExistingState create(ClassInfo classInfo) {
-      return new AutoValue_AbstractClassEntryState_ExistingState(Optional.of(classInfo));
+    public static ExistingState create(ClassInfo classInfo, boolean direct) {
+      return new AutoValue_AbstractClassEntryState_ExistingState(Optional.of(classInfo), direct);
     }
 
     @Override
@@ -89,6 +90,11 @@
     public Optional<ClassInfo> classInfo() {
       return Optional.empty();
     }
+
+    @Override
+    public boolean direct() {
+      return true;
+    }
   }
 
   /**
@@ -101,7 +107,7 @@
     public static IncompleteState create(
         ClassInfo classInfo, ResolutionFailureChain resolutionFailureChain) {
       return new AutoValue_AbstractClassEntryState_IncompleteState(
-          Optional.of(classInfo), resolutionFailureChain);
+          Optional.of(classInfo), /* direct= */ true, resolutionFailureChain);
     }
 
     public abstract ResolutionFailureChain resolutionFailureChain();
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
index e7e335e..a632d2a 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ClassCache.java
@@ -22,6 +22,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableSortedMap;
 import com.google.common.io.Closer;
 import com.google.devtools.build.importdeps.AbstractClassEntryState.ExistingState;
 import com.google.devtools.build.importdeps.AbstractClassEntryState.IncompleteState;
@@ -33,7 +34,6 @@
 import java.io.PrintStream;
 import java.nio.file.Path;
 import java.util.HashMap;
-import java.util.HashSet;
 import java.util.Map;
 import java.util.Objects;
 import java.util.Optional;
@@ -74,7 +74,7 @@
     return entry.getState(lazyClasspath);
   }
 
-  public ImmutableList<Path> collectUsedJarsInRegularClasspath() {
+  public ImmutableMap<Path, Boolean> collectUsedJarsInRegularClasspath() {
     return lazyClasspath.collectUsedJarsInRegularClasspath();
   }
 
@@ -88,18 +88,19 @@
     private final String internalName;
     private final ZipFile zipFile;
     private final Path jarPath;
-    private final boolean direct;
+    private final boolean isDirectDep;
 
     /**
      * The state of this class entry. If {@literal null}, then this class has not been resolved yet.
      */
     @Nullable private AbstractClassEntryState state = null;
 
-    private LazyClassEntry(String internalName, ZipFile zipFile, Path jarPath, boolean direct) {
+    private LazyClassEntry(
+        String internalName, ZipFile zipFile, Path jarPath, boolean isDirectDep) {
       this.internalName = internalName;
       this.zipFile = zipFile;
       this.jarPath = jarPath;
-      this.direct = direct;
+      this.isDirectDep = isDirectDep;
     }
 
     ZipFile getZipFile() {
@@ -132,13 +133,21 @@
       if (isResolved()) {
         return;
       }
-      resolveClassEntry(this, lazyClasspath);
+      resolveClassEntry(this, lazyClasspath, /* explicitUse= */ true);
       checkNotNull(state, "After resolution, the state cannot be null");
     }
 
-    private static void resolveClassEntry(LazyClassEntry classEntry, LazyClasspath lazyClasspath) {
+    private static void resolveClassEntry(
+        LazyClassEntry classEntry, LazyClasspath lazyClasspath, boolean explicitUse) {
       if (classEntry.state != null) {
         // Already resolved. See if it is the existing state.
+        if (classEntry.state instanceof ExistingState) {
+          ExistingState state = (ExistingState) classEntry.state;
+          if (!state.direct() && explicitUse) {
+            // If the state was previously indirect, update now for direct dep
+            classEntry.state = ExistingState.create(state.classInfo().get(), explicitUse);
+          }
+        }
         return;
       }
 
@@ -157,7 +166,7 @@
           failurePath.map(resolutionFailureChainsBuilder::add);
         }
         ClassInfoBuilder classInfoBuilder =
-            new ClassInfoBuilder().setJarPath(classEntry.jarPath).setDirect(classEntry.direct);
+            new ClassInfoBuilder().setJarPath(classEntry.jarPath).setDirect(classEntry.isDirectDep);
         // Only visit the class if we need to extract its list of members.  If we do visit, skip
         // code and debug attributes since we just care about finding declarations here.
         if (lazyClasspath.populateMembers) {
@@ -173,7 +182,8 @@
             resolutionFailureChainsBuilder.build();
         if (resolutionFailureChains.isEmpty()) {
           classEntry.state =
-              ExistingState.create(classInfoBuilder.build(lazyClasspath, /*incomplete=*/ false));
+              ExistingState.create(
+                  classInfoBuilder.build(lazyClasspath, /*incomplete=*/ false), explicitUse);
         } else {
           ClassInfo classInfo = classInfoBuilder.build(lazyClasspath, /*incomplete=*/ true);
           classEntry.state =
@@ -199,7 +209,7 @@
       if (superClassEntry == null) {
         return Optional.of(ResolutionFailureChain.createMissingClass(superName));
       } else {
-        resolveClassEntry(superClassEntry, lazyClasspath);
+        resolveClassEntry(superClassEntry, lazyClasspath, /* explicitUse= */ false);
         AbstractClassEntryState superState = superClassEntry.state;
         if (superState instanceof ExistingState) {
           // Do nothing. Good to proceed.
@@ -268,7 +278,7 @@
           .orElse(null);
     }
 
-    public ImmutableList<Path> collectUsedJarsInRegularClasspath() {
+    public ImmutableMap<Path, Boolean> collectUsedJarsInRegularClasspath() {
       return regularClasspath.collectUsedJarFiles();
     }
 
@@ -308,15 +318,18 @@
       return classIndex.get(internalName);
     }
 
-    public ImmutableList<Path> collectUsedJarFiles() {
-      HashSet<Path> usedJars = new HashSet<>();
+    /** Second argument in the Map is if the jar is used directly (at least once). */
+    public ImmutableMap<Path, Boolean> collectUsedJarFiles() {
+      Map<Path, Boolean> usedJars = new HashMap<>();
       for (Map.Entry<String, LazyClassEntry> entry : classIndex.entrySet()) {
         LazyClassEntry clazz = entry.getValue();
         if (clazz.isResolved()) {
-          usedJars.add(clazz.jarPath);
+          if (!usedJars.containsKey(clazz.jarPath) || clazz.state.direct()) {
+            usedJars.put(clazz.jarPath, clazz.state.direct());
+          }
         }
       }
-      return ImmutableList.sortedCopyOf(usedJars);
+      return ImmutableSortedMap.copyOf(usedJars);
     }
 
     private void printClasspath(PrintStream stream) {
diff --git a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
index 91b706c..40b7491 100644
--- a/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
+++ b/src/java_tools/import_deps_checker/java/com/google/devtools/build/importdeps/ImportDepsChecker.java
@@ -15,6 +15,7 @@
 
 import com.google.common.collect.HashMultimap;
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.devtools.build.importdeps.AbstractClassEntryState.IncompleteState;
 import com.google.devtools.build.importdeps.ResultCollector.MissingMember;
@@ -105,12 +106,14 @@
   /** Emit the jdeps proto. The parameter ruleLabel is optional, indicated with the empty string. */
   public Dependencies emitJdepsProto(String ruleLabel) {
     Dependencies.Builder builder = Dependencies.newBuilder();
-    ImmutableList<Path> paths = classCache.collectUsedJarsInRegularClasspath();
-    // TODO(b/77723273): Consider "implicit" for Jars only needed to resolve supertypes
+    ImmutableMap<Path, Boolean> paths = classCache.collectUsedJarsInRegularClasspath();
     paths.forEach(
-        path ->
+        (path, explicit) ->
             builder.addDependency(
-                Dependency.newBuilder().setKind(Kind.EXPLICIT).setPath(path.toString()).build()));
+                Dependency.newBuilder()
+                    .setKind(explicit ? Kind.EXPLICIT : Kind.IMPLICIT)
+                    .setPath(path.toString())
+                    .build()));
     return builder.setRuleLabel(ruleLabel).setSuccess(true).build();
   }
 
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
index af6a52e..6ac5a33 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/ClassCacheTest.java
@@ -192,7 +192,7 @@
                   .getClassState("com/google/devtools/build/importdeps/testdata/Library$Class9")
                   .isIncompleteState())
           .isTrue();
-      assertThat(cache.collectUsedJarsInRegularClasspath()).containsExactly(libraryJar);
+      assertThat(cache.collectUsedJarsInRegularClasspath()).containsExactly(libraryJar, true);
 
       assertThat(
               cache
@@ -200,7 +200,7 @@
                   .isIncompleteState())
           .isTrue();
       assertThat(cache.collectUsedJarsInRegularClasspath())
-          .containsExactly(libraryJar, libraryAnnotationsJar);
+          .containsExactly(libraryJar, true, libraryAnnotationsJar, true);
 
       assertThat(
               cache
@@ -208,7 +208,28 @@
                   .isIncompleteState())
           .isTrue();
       assertThat(cache.collectUsedJarsInRegularClasspath())
-          .containsExactly(libraryJar, libraryAnnotationsJar, libraryInterfaceJar);
+          .containsExactly(
+              libraryJar, true, libraryAnnotationsJar, true, libraryInterfaceJar, true);
+    }
+  }
+
+  @Test
+  public void testJdepsOutput_withSuperclasses_hasImplicitDeps() throws IOException {
+    try (ClassCache cache =
+        new ClassCache(
+            ImmutableSet.of(bootclasspath),
+            ImmutableSet.of(libraryJar, libraryInterfaceJar),
+            ImmutableSet.of(libraryJar, libraryInterfaceJar),
+            ImmutableSet.of(clientJar),
+            /*populateMembers=*/ true)) {
+
+      assertThat(
+              cache
+                  .getClassState("com/google/devtools/build/importdeps/testdata/Client")
+                  .isExistingState())
+          .isTrue();
+      assertThat(cache.collectUsedJarsInRegularClasspath())
+          .containsExactly(libraryJar, false, libraryInterfaceJar, false);
     }
   }
 
diff --git a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
index 9cf9e35..08f559d 100644
--- a/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
+++ b/src/java_tools/import_deps_checker/javatests/com/google/devtools/build/importdeps/LazyClassEntryStateTest.java
@@ -39,11 +39,12 @@
 
   @Test
   public void testExistingState() {
-    ExistingState state = ExistingState.create(LIST_CLASS_INFO);
+    ExistingState state = ExistingState.create(LIST_CLASS_INFO, /* direct= */ true);
 
     assertThat(state.isExistingState()).isTrue();
     assertThat(state.isIncompleteState()).isFalse();
     assertThat(state.isMissingState()).isFalse();
+    assertThat(state.direct()).isTrue();
 
     assertThat(state.asExistingState()).isSameInstanceAs(state);
     assertThrows(IllegalStateException.class, () -> state.asIncompleteState());